package 贪心算法;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class 拼接最大数 {
    public static int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int n1 = nums1.length;
        int n2 = nums2.length;

        int min = Math.min(k, Math.min(n1,n2));
        int max = 0;
        int[] res = new int[k];
        for (int i = 0; i <= k; i++) {
            if (i > n1 || k-i > n2){
                continue;
            }
            int[] res1 = removeKdigits(nums1, i);
            int[] res2 = removeKdigits(nums2, k-i);
            if (res1 == null){
                res = compare(res,res2);
                continue;
            }else if (res2 == null){
                res = compare(res,res1);
                continue;
            }
            int m = 0,n=0,j=0;
            int[] resArray = new int[k];
            int length1 = res1.length;
            int length2 = res2.length;
            while (m< length1 || n< length2){
                if (m == length1){
                    resArray[j] = res2[n];
                    n++;
                    j++;
                    continue;
                }
                if (n== length2){
                    resArray[j] = res1[m];
                    m++;
                    j++;
                    continue;
                }
                if (res1[m]>res2[n]){
                    resArray[j] = res1[m];
                    m++;
                }else if (res1[m]<res2[n]){
                    resArray[j] = res2[n];
                    n++;
                }else {
                    int nn = n+1;
                    int mm = m+1;
                    while (mm < length1 && nn < length2 && res1[mm]==res2[nn]){
                        nn++;
                        mm++;
                    }
                    if (mm==length1 || (nn<length2&& res2[nn] > res1[mm])){
                        resArray[j] = res2[n];
                        n++;
                    }else {
                        resArray[j] = res1[m];
                        m++;
                    }
                }
                j++;
            }
            res = compare(res,resArray);
        }
        return res;
    }

    private static int[] compare(int[] num1,int[] num2){
        int n = num1.length;
        for (int i = 0; i < n; i++) {
            if (num1[i] > num2[i]){
                return num1;
            }else if (num2[i] > num1[i]){
                return num2;
            } else {
                continue;
            }
        }
        return num1;
    }

    private static int[] removeKdigits(int[] num,int k){
        if (k==0){
            return null;
        }
        int n = num.length;
        if (k > n){
            return null;
        }
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(num[0]);
        int times = 0;
        for (int i = 1;i<n;i++) {
            while (!stack.isEmpty() && times <  n-k && num[i] > stack.peek()){
                Integer pop = stack.pop();
                times ++;
            }
            stack.push(num[i]);
        }
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = stack.pollLast();
        }
        return res;
    }


    public static void main(String[] args) {
        int[] nums1 = {9,1,2,5,8,3};
        int[] nums2 = {3,4,6,5};
        System.out.println(Arrays.toString(maxNumber(nums1, nums2, 5)));

    }
}
